It has been conventionally known that exclusive control is carried out on partial sections of programs to be parallelly executed for sequential execution.
Recent OS's or programming languages support a program executing function of operating a plurality of “threads” called “multi-thread” parallelly or pseudo-parallelly on a multi-processor based on time division. In this connection, the word “thread” refers to an execution entity sharing the memory space of a computer system.
Thread processing, which is different from conventional divided processing units, shares the memory space and other computer resources. Thus the thread processing is advantageous in that sharing of data between a plurality of threads can be facilitated with a low execution overhead.
For example, Java (registered trademark) as a sort of programming language supports the multi-thread at language level, improves program performance on a multi-processor system, and facilitates short and clear description of processing requiring simultaneous execution of a plurality of jobs in a network server, a GUI application or the like.
In a program supporting the multi-thread function, a plurality of threads are processed simultaneously and parallelly. Thus, when the plurality of threads are operated simultaneously and parallelly on the same object (data), this may cause possible inconsistency in the state of the object. To avoid this, Java prepares a synchronization function (exclusive control function) called “monitor” to enable exclusive control between the threads. The word “exclusive control” as used therein refers to such control as to cause only one thread to operate an object to avoid an disadvantage involved by a plurality of threads which operate the same object at the same timing.
The monitor, which has a data structure having data to be subjected to the exclusive control and an exclusive access procedure thereto as a set, is configured so that, when executing a critical section, only one thread at most can execute it. The word “critical section” as used therein refers to a section which is specified by the user and exclusively executed by the program.
To this end, each thread locks an object to be operated at the entrance of the critical section and unlocks the object at the exit of the critical section.
When the object to be locked is already locked by another thread, the execution thereof is awaited until the object is unlocked. In this manner, the exclusive execution of the program in the critical section can be carried out. A class library in Java is designed on the assumption that the class library is used in a multi-thread environment.
In many programs, meanwhile, it is experimentally known that most of objects generated upon execution are not referred to by a plurality of threads. The word “to refer” as used therein means that a system or a program acquires the content of an object while not changing the property of the object. In the implementation of a conventional virtual machine (which will be referred to merely VM, hereinafter), high speed processing is realized by considering the fact that a thread requiring such exclusive control is localized (locality).
For example, refer to a non-patent literature 1, D. Bacon and R. Konuru and C. Murthy and M. Serrano, Thin Locks: Featherweight Synchronization for Java, In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, 1998. In the literature 1, a high-speed system called “Thin Locks” is proposed.
In the Thin Locks, while an object is locked by a single thread, the locking and unlocking of the object are carried out with a low overhead by writing information about the locking thread in a region reserved in a header of the object.
When a plurality of threads simultaneously require the execution of a critical section, the header of the object is changed to designate a data structure externally reserved for exclusive control.
When the plurality of threads require the execution of a critical section, the operation of the externally-reserved data structure is required. However, when the lock by only a single thread is carried out, the locking and unlocking thereof can be realized only through the operation of the header, thus realizing a high-speed exclusive processing.
As another system other than such an overhead reduction system for dynamic exclusive control, there is proposed an optimization system which removes unnecessary exclusive control by analyzing a program.
For example, refer to non-patent literature 2, J. D. Choi, Escape Analysis for Java, In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, Applications, 1999. In the literature 2, there is proposed a system for removing unnecessary exclusive control by performing program analysis called “escape analysis”.
The escape analysis is a technique for analyzing whether or not an object generated in a program can be shared by a plurality of threads. When the fact that the object cannot be shared by the plurality of threads is ensured through the analysis of the above technique, the exclusive control for the object becomes unnecessary and therefore this function can be eliminated.
The prior art exclusive high-speed technique is limited only to the situation where (1) exclusive control is required only by a single thread or (2) compiler ensures that exclusive control is unnecessary due to data not shared by a plurality of threads.
Accordingly, in situations other than the aforementioned situations, the execution of an instruction in a critical section is exclusively carried out even when data can, in practical case, be executed simultaneously, as when the data are merely referred to. In the critical section, even when the data are merely referred to by threads, the thread in question has to await its own order or sequence. That is, as a whole, the exclusive control is executed sequentially on the plurality of threads.